package com.fengye.algorithms.alibaba;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author fengye
 * @Date 2023/4/11 9:43
 **/
public class MaxSubArray30 {

    public List maxSubArray(int nums[]) {
        int[] dp = new int[nums.length];
        int maxlength = 0;// 最大连续数组，最大length
        int startIndex = 0;//  最大连续数组开始标记
        int max = dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            // 这里必须>=保证maxLength最长
            if(dp[i-1] + nums[i] >= nums[i]) {
                dp[i] = dp[i-1] + nums[i];
                maxlength++;
            } else {
                dp[i] = nums[i];
                startIndex = i;
                maxlength = 1;
            }

            max = Math.max(max,dp[i]);
        }

        List<Integer> list = new ArrayList<>();
        list.add(max);
        list.add(startIndex);
        list.add(maxlength);
        return list;
    }
}
